package com.mdnote.algorithm;

import java.util.Arrays;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/10 
 * @description 地界斯特拉算法
 */
public class DijkstraAlgorithm {

    private static final Integer INF = 65535;
    /**
     * 是否访问多，0 未访问 1 已访问
     */
    private int[] isVisited;

    /**
     * 前驱节点
     */
    private int[] preVertex;
    
    /**
     * 路程
     */
    private int[] distances;

    /**
     * 地界斯特拉入口
     * @param mGraph 图
     * @param startIndex 起点
     */
    public void dijkstra(MGraph mGraph, int startIndex) {
        // 初始化三个数组，并把第一步的访问设为1
        this.init(mGraph, startIndex);
        // 计算第一步走出去的节点和周围节点的距离，把距离写在distance上，并把startVertex设置为他们的前驱节点
        update(mGraph, startIndex);
        // 走出第二、第三...步
        for (int i = 1; i < mGraph.vertexCount; i++) {
            // 找到下一步要去那个节点
            int index = selectMinDistance();
            // 更新他们到轴距离
            update(mGraph, index);

        }

    }

    /**
     * 找到下一步应该怎么走
     * @return 往哪边走
     */
    private int selectMinDistance() {
        int min = INF;
        int index = 0;
        for (int i = 0; i < this.distances.length; i++) {
            if (isVisited[i] == 0 && this.distances[i] < min) {
                min = this.distances[i];
                index = i;
            }
        }
        return index;
    }

    /**
     * 初始化
     * @param mGraph
     * @param startIndex
     */
    private void init(MGraph mGraph, int startIndex) {
        this.isVisited = new int[mGraph.vertexCount];
        this.distances = new int[mGraph.vertexCount];
        this.preVertex = new int[mGraph.vertexCount];

        Arrays.fill(this.distances, INF);
        Arrays.fill(this.preVertex, -1);

        // 第一步已经走过了
        this.isVisited[startIndex] = 1;
        this.distances[startIndex] = 0;
    }

    /**
     * 移动一步
     * @param mGraph 图
     * @param index 位置
     */
    private void update(MGraph mGraph, int index) {
        // 先标记为已访问
        this.isVisited[index] = 1;
        // 更新距离数组
        int dis = 0;
        for (int i = 0; i < mGraph.weights[index].length; i++) {
            // 只处理相互连接的点
            if (mGraph.weights[index][i] != INF) {
                // 计算出走出下一步的总路程
                dis = this.distances[index] + mGraph.weights[index][i];
                // 如果这个几点没有访问过且计算得到的距离比数组里面的值还小，我们可以认为目前这样走是最好的
                if (isVisited[i] == 0 && dis < this.distances[i]) {
                    // 更新各个点的总距离
                    this.distances[i] = dis;
                    // 更新索引
                    this.preVertex[i] = index;
                }
            }

        }
    }

    /**
     * 获取路径
     * @param index 终点
     */
    public void getPath(MGraph mGraph, int index) {
        int temp = index;

         while (true){
             if (temp > 0) {
                 System.out.print(mGraph.vertex[temp] + " ");
                 temp = this.preVertex[temp];
             } else {
                 break;
             }
         }
    }

    /**
     * 显示
     */
    public void show(MGraph mGraph) {
        for (int i = 0; i < mGraph.vertex.length; i++) {
            System.out.print(mGraph.vertex[i] + "(" + this.distances[i] + ") ");
        }
    }

    public static void main(String[] args) {
        DijkstraAlgorithm dijkstraAlgorithm = new DijkstraAlgorithm();

        MGraph mGraph = new MGraph(7);
        mGraph.setVertex(new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'});
        mGraph.setWeights(new int[][]{
                {INF,   5,   7, INF, INF, INF,   2},
                {  5, INF, INF,   9, INF, INF,   3},
                {  7, INF, INF, INF,   8, INF, INF},
                {INF,   9, INF, INF, INF,   4, INF},
                {INF, INF,   8, INF, INF,   5,   4},
                {INF, INF, INF,   4,   5, INF,   6},
                {  2,   3, INF, INF,   4,   6, INF}
        });
        dijkstraAlgorithm.dijkstra(mGraph, 6);
        dijkstraAlgorithm.show(mGraph);
        System.out.println();
        System.out.println(Arrays.toString(dijkstraAlgorithm.preVertex));
        System.out.println();
        dijkstraAlgorithm.getPath(mGraph, 1);
    }
    
    private static class MGraph {

        private int vertexCount;
        private char[] vertex;
        private int[][] weights;

        public MGraph(int vertexCount) {
            this.vertexCount = vertexCount;
        }

        public void setVertex(char[] vertex) {
            this.vertex = vertex;
        }

        public void setWeights(int[][] weights) {
            this.weights = weights;
        }


    }
    
}
